package cn.edu.anan.algorithm.sort;

import java.util.Arrays;

/**
 * 插入排序：
 *  1.时间复杂度：
 *      O(n^2)
 *  2.空间复杂度：
 *      O(1)是原地排序算法
 * 3.算法稳定性：
 *     是稳定排序算法
 */
public class InsertSort {

    /**
     * 插入排序
     * @param array：待排序数组
     * @param n：待排序数组大小
     */
    public static void sort(Integer [] array,int n) {
        // 如果排序数组规模小于等于1，直接返回
        if (n <= 1) {
            return;
        }

        // 将数据分为两个区域：
        // 有序数据区域：array[0]
        // 无序数据区域：array[1]...array[n-1]
        // 循环遍历无序区域的数据，插入到有序数据区域
        for(int i = 1; i < n; i++){
            // 临时存储待插入目标元素
            int tmp = array[i];
            // 有序区域最后一个元素下标
            int j = i - 1;
            // 从后往前查找插入位置,并移动数据
            for(; j >= 0;j--){
                if(array[j] > tmp){
                    // 向后移动数据
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }

            // 插入数据
            System.out.println("第【" + i + "】次插入排序");
            array[j+1] = tmp;
        }
    }

}
